package 串;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:求模式串的next函数
 * User:Mr.Du
 * Date:2021/8/24
 * Time:16:36
 */
public class Next {

    public static void main(String[] args) {
        int[] array = next("babaabbb");
        for(int i = 0;i<array.length;i++){
            array[i] += 1;
        }
        System.out.println(Arrays.toString(array));
    }

    private static int[] next(String s) {   //传过来的时模式串,返回的是next数组
        int len = s.length();                  //获取模式串的长度
        char[] p = s.toCharArray();             //把模式串转换成char数组
        int[] next = new int[len];              //声明next数组,最后返回
        next[0] = -1;            //第一位肯定是-1
        next[1] = 0;             //第二位肯定是0
        int j = 1;               //遍历next数组用
        int k = 0;                 //next[j]=k  k就是next数组中的值

        while (j < len - 1){
            if (k == -1){        //回溯到0都不匹配,则next值为0
                j++;
                k = 0;
                next[j] = 0;
            } else if (p[j] == p[k]){     //找到了匹配的,对应next值+1
                j++;
                k++;
                next[j] = k;
            } else {                    //不匹配,指针回溯
                k = next[k];
            }
        }
        return next;        //返回next数组
    }
}
